/**
 * 
 */
package leetCode;

/**
 * @author zhong
 *
 */
public class DominoandTrominoTiling {
	public int numTilings(int N) {
		int k = 0;
		int sum = 0;
		int mod = 1000000007;
		int Limit = N / 3;
		int pow = 1;
		while (k <= Limit) {
			sum += (C(N - 2 * k, k, mod) * pow) % mod;
			sum %= mod;
			pow <<= 1;// 2^k
			pow %= mod;
			k++;
		}
		return sum;
	}

	private int C(int i, int k, int mod) {
		double fenmu = 1;
		double fenzi = 1;
		for (; k > 0; k--, i--) {
			fenmu *= k;
			fenmu %= mod;
			fenzi *= i;
			fenzi %= mod;
		}
		double res = fenzi / fenmu;
		if (res < 1)
			res *= mod;
		return (int) res;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println(new DominoandTrominoTiling().numTilings(3));
	}

}
